package com.zhang.sort;

import java.util.ArrayList;
import java.util.List;

/**
 * @author zhang
 * @time 2022/01/11 19:38:52
 */
public class QuickSortGao {
    public static List<Integer> quickSort(List<Integer> list) {
        // 如果集合中只有1个或没有元素，也就不用排序了，就结束递归
        if (list.size() < 2) {
            return list;
        }

        // 以集合中的第一个元素为参考元素，把比参考元素大的，和比它小的分别放入不同的集合中
        int pivot = list.get(0);
        List<Integer> left = new ArrayList<>();
        List<Integer> middle = new ArrayList<>();
        List<Integer> right = new ArrayList<>();

        for (Integer n : list) {
            if (n < pivot) {
                left.add(n);
            } else if (n > pivot) {
                right.add(n);
            } else {
                middle.add(n);
            }
        }

        // 以下代码的伪代码：quickSort(left) + middle + quickSort(right)
        left = quickSort(left);
        right = quickSort(right);
        left.addAll(middle);
        left.addAll(right);
        return left;
    }

}
